package leo.mystudy.leetcode.nodelist;

import leo.mystudy.leetcode.ListNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author leo
 * @version 1.0.0
 * @description 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：head = [4,2,1,3]
 * 输出：[1,2,3,4]
 * 示例 2：
 * <p>
 * <p>
 * 输入：head = [-1,5,3,4,0]
 * 输出：[-1,0,3,4,5]
 * 示例 3：
 * <p>
 * 输入：head = []
 * 输出：[]
 *  
 * <p>
 * 提示：
 * <p>
 * 链表中节点的数目在范围 [0, 5 * 104] 内
 * -105 <= Node.val <= 105
 *  
 * <p>
 * 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xa262d/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * @create 2022/3/15 19:33
 */
public class SortList {
    public ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }
        List<Integer> list = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }
        list.sort((Integer::compareTo));
        return build(list);
    }
    public ListNode build(List<Integer> arr) {
        if (arr == null || arr.size() == 0) {
            return null;
        }
        ListNode head = new ListNode(arr.get(0));
        if (arr.size() == 1) {
            return head;
        }
        ListNode cur = head;
        for (int i = 1; i < arr.size(); i++) {
            ListNode node = new ListNode(arr.get(i));
            cur.next = node;
            cur = node;
        }
        return head;
    }
//    public ListNode sortList(ListNode head) {
//        // 冒泡排序法
//        ListNode endPoint = null;
//        ListNode cur = head;
//        ListNode next;
//        ListNode pre = null;
//        while ((next = cur.next) != endPoint) {
//            if (cur.val > next.val) {
//                // 如果当前值大于next值，交换
//                cur.next = next.next;
//                next.next = cur;
//                cur = next;
//                if (pre != null) {
//                    pre.next = cur;
//                }
//                if (cur.next == head) {
//                    // 如果交换的第一个节点，将head替换
//                    head = cur;
//                }
//            }
//            pre = cur;
//            cur = cur.next;
//            if (cur.next == endPoint) {
//                endPoint = cur;
//                cur = head;
//            }
//        }
//        return head;

//    }

    public static void main(String[] args) {
        ListNode listNode = ListNode.build(new int[]{1, 3, 2, 9, 7});
        listNode = new SortList().sortList(listNode);
        System.out.println(listNode);
    }
}
